package com.lims.algorithm.algset.breadth_search.questions;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * <功能简述> n维数组中，求出最大数目的连续的1的块（连续1:表示某个值为1的点，其上下左右至少还有一个值为1的点与之连接）
 *
 * @author lims
 * @date 2020-09-10 11:38
 */
public class ContinuousNum {
    /**
     * 坐标类，记录点在二维数组中的索引
     */
    static class Coordinate {
        int x;
        int y;

        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static int calcuContinuNumBFS(int[][] arr) {
        // 辅助队列
        Queue<Coordinate> queue = new LinkedBlockingQueue<>();
        // 所有1的点坐标集
        List<Coordinate> nonZeroPoints = new ArrayList<>();
        // 点访问标记，已访问置为true
        boolean[][] isVisited = new boolean[arr.length][arr[0].length];
        // 结果的最大值
        int max = 0;

        // 初始化值，方便计算使用
        for (int i = 0; i < arr.length; ++i) {
            for (int j = 0; j < arr[i].length; ++j) {
                if (arr[i][j] == 1) {
                    Coordinate coordinate = new Coordinate(i, j);
                    nonZeroPoints.add(coordinate);
                }
            }
        }

        // 对每个未访问的“1”点进行广度优先搜索
        for (int p = 0; p < nonZeroPoints.size(); ++p) {
            Coordinate coordinate = nonZeroPoints.get(p);
            if (!isVisited[coordinate.x][coordinate.y]) {
                // 第一个未访问的1入队头
                queue.offer(coordinate);
                isVisited[coordinate.x][coordinate.y] = true;
                // 每个连续1的块中 1的数目
                int numSimpleBFS = calcuContinuNumBFS(arr, queue, isVisited);
                if (max < numSimpleBFS) {
                    max = numSimpleBFS;
                }
            }
        }
        return max;
    }

    /**
     * 每个坐标点进行广度优先搜索
     *
     * @param queue
     * @param isVisited
     * @return
     */
    private static int calcuContinuNumBFS(int[][] arr, Queue<Coordinate> queue, boolean[][] isVisited) {
        int tempNum = 0;
        while (!queue.isEmpty()) {
            // 取出队列头 计数并置为已访问
            Coordinate pollCor = queue.poll();
            int quePX = pollCor.x;
            int quePY = pollCor.y;
            tempNum++;
            // 对pollCor点上、下、左、右的邻接点判断，符合未访问1的点入队列
            if ((quePX - 1) >= 0 && !isVisited[quePX - 1][quePY] && arr[quePX - 1][quePY] == 1) {
                Coordinate upCor = new Coordinate(quePX - 1, quePY);
                queue.offer(upCor);
                isVisited[quePX - 1][quePY] = true;
            }
            if ((quePX + 1) < arr.length && !isVisited[quePX + 1][quePY] && arr[quePX + 1][quePY] == 1) {
                Coordinate downCor = new Coordinate(quePX + 1, quePY);
                queue.offer(downCor);
                isVisited[quePX + 1][quePY] = true;
            }
            if ((quePY - 1) >= 0 && !isVisited[quePX][quePY - 1] && arr[quePX][quePY - 1] == 1) {
                Coordinate leftCor = new Coordinate(quePX, quePY - 1);
                queue.offer(leftCor);
                isVisited[quePX][quePY - 1] = true;
            }
            if ((quePY + 1) < arr[quePX].length && !isVisited[quePX][quePY + 1] && arr[quePX][quePY + 1] == 1) {
                Coordinate rightCor = new Coordinate(quePX, quePY + 1);
                queue.offer(rightCor);
                isVisited[quePX][quePY + 1] = true;
            }
        }
        return tempNum;
    }

    /*********************************************************/
    public static void main(String[] args) {
        int[][] arr = {
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 1, 0, 0, 1, 1, 1, 1, 1},
                {0, 1, 1, 0, 0, 1, 1, 1, 1, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0, 0},
        };
        System.out.println(calcuContinuNumBFS(arr));
    }
}














